package c01_array;

import lombok.extern.slf4j.Slf4j;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 *
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 *
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
@Slf4j
public class S16 {
    static int[] nums;
    static int target;
    public static void test() {
        nums = new int[]{-1,2,1,-4};
        target=1;
    }
    public static void test1() {
        nums = new int[]{1,1,-1,-1,3};
        target=-1;
    }
    public static void test2() {
        nums=new int[]{-7,-71,-7,-13,45,46,-50,83,-29,-72,9,32,-74,81,68,92,-31,28,-46,-86,-70,31,-62,-20,-56,97,-41,21,81,17,-14,56,69,16,25,-38,65,-48,15,16,-25,68,-41,46,-56,-2,-3,82,8,19,-32,62,92,-56,-9,43,50,100,66,-45,41,-24,-4,83,-36,79,24,97,82,89,-56,-91,75,-64,-68,96,-55,-52,-58,-37,68,27,89,-40,-42,94,-92,-70,40,74,75,-15,54,-54,0,4,-39,93,88,-31,-26,93,8,-85,-62,89,-93,98,4,-58,8,5,-93,7,30,-75,63,41,62,-52,49,93,-11,87,7,52,5,-96,-56,43,-41,-75,-16,73,6,35,-32,62,-50,-57,-25,5,-32,94,-70,6,19,-12,63,-47,76,-57,41,-49,-33,-15,-81,55,88,67,-51,100,-19,-39,62,84,-100,78,-24,31,-32,-83,33,-25,86,9,-30,-40,52,64,-30,-17,19,-69,-89,-67,-79,-100,-53};
        target=157;
    }
    public static void main(String[] args) {
        S16 s16 = new S16();
       // int[] mums = new int[]{-1,2,1,-4};
      //  int[] mums = new int[]{0,2,1,-3};
    //    int[] mums = new int[]{1,1,-1,-1,3};

    //    int target = -1;
        test2();
        int gap = s16.threeSumClosest(nums, target);
        System.out.println(gap);
    }
    public int threeSumClosest(int[] nums, int target) {
        int minGap = Integer.MAX_VALUE;
        int closetNum = Integer.MAX_VALUE;
        minGap=getGap(nums,0,1,2,target);
        for (int i = 0; i < nums.length; i++) {
     //       log.error("i: {}",i);
            for (int j = i+1; j < nums.length; j++) {
     //           log.warn("j: {}",j);
                int[] minMaxArr = getTarget(nums[i], nums[j], target, minGap);
                for (int k = j+1; k < nums.length; k++) {
                    //小于最小值, 不需要考虑重复
                    if(nums[k]<minMaxArr[0]) continue;
                    //大于最大值
                    if(nums[k]>minMaxArr[1]) continue;

                    log.info("getGap: i={},j={},k={},target={}",i,j,k,target);
                    //介于最小值和最大值之间
                    int currentGap = getGap(nums, i, j, k, target);
                    closetNum=getSum(nums,i,j,k);
                    log.error("currentGap:{}",currentGap);
                    minGap=currentGap;
                    minMaxArr = getTarget(nums[i], nums[j], target, minGap);
                }
            }
        }

        return closetNum;
    }
    public int getSum(int[] nums , int i,int j,int k) {
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        return nums[i]+nums[j]+nums[k];
    }
    public int getGap(int[] nums , int i,int j,int k,int target) {
   //     log.info("getGap: i={},j={},k={},target={}",i,j,k,target);
  //      log.info("getGap---------------->value: i={},j={},k={},target={}",nums[i],nums[j],nums[k],target);
        return Math.abs(target-nums[i]-nums[j]-nums[k]);
    }
    public int[] getTarget(int a , int b , int target ,int gap) {
        int[] arr = new int[2];
        arr[0]=target-gap-a-b;
        arr[1]=target+gap-a-b;
        return arr;
    }

}
